package com.zx._12_算法.数据结构.stack;

public class Demo2 {

    // 计算逆波兰表达式
    // 逆波兰表达式，也叫后缀表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式
    // ["4", "13", "5", "/", "+"] 等价于(4 + (13 / 5)) = 6
    // ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] 等价于((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22
    public static void main(String[] args) {
        String[][] ps = {
                {"4", "13", "5", "/", "+"}, // 结果=6
                {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}// 结果=22
        };

        System.out.println("机构1");
        for (String[] arr : ps) {
            Stack<String> stack = new Stack<>();
            for (String num : arr) {
                int n = 0;
                switch (num) {
                    case "+":
                        String right = stack.pop();
                        String left = stack.pop();
                        n = Integer.parseInt(left) + Integer.parseInt(right);
                        break;
                    case "-":
                        right = stack.pop();
                        left = stack.pop();
                        n = Integer.parseInt(left) - Integer.parseInt(right);
                        break;
                    case "*":
                        right = stack.pop();
                        left = stack.pop();
                        n = Integer.parseInt(left) * Integer.parseInt(right);
                        break;
                    case "/":
                        right = stack.pop();
                        left = stack.pop();
                        n = Integer.parseInt(left) / Integer.parseInt(right);
                        break;
                    default:
                        n = Integer.parseInt(num);
                        break;
                }
                stack.push(n + "");
            }
            System.out.println(stack.pop());
        }

        System.out.println("机构2");
        for (String[] arr : ps) {
            Stack2<String> stack = new Stack2<>();
            for (String num : arr) {
                int n = 0;
                switch (num) {
                    case "+":
                        String right = stack.pop();
                        String left = stack.pop();
                        n = Integer.parseInt(left) + Integer.parseInt(right);
                        break;
                    case "-":
                        right = stack.pop();
                        left = stack.pop();
                        n = Integer.parseInt(left) - Integer.parseInt(right);
                        break;
                    case "*":
                        right = stack.pop();
                        left = stack.pop();
                        n = Integer.parseInt(left) * Integer.parseInt(right);
                        break;
                    case "/":
                        right = stack.pop();
                        left = stack.pop();
                        n = Integer.parseInt(left) / Integer.parseInt(right);
                        break;
                    default:
                        n = Integer.parseInt(num);
                        break;
                }
                stack.push(n + "");
            }
            System.out.println(stack.pop());
        }

    }
}
